package com.lun.swordtowardoffer2.c15;

public class LongestIncreasingPath {
	
	public int longestIncreasingPath(int[][] matrix) {
		if(matrix.length == 0 || matrix[0].length == 0) {
			return 0;
		}
		
		//缓存
		int[][] lengths = new int[matrix.length][matrix[0].length];
		
		int max = 0;
		
		for(int i = 0; i < matrix.length; i++) {
			for(int j = 0; j < matrix[0].length; j++) {
				int length = dfs(matrix, lengths, i, j);
				max = Math.max(max, length);
			}
		}
		
		return max;
	}

	private int dfs(int[][] matrix, int[][] lengths, int i, int j) {
		if(lengths[i][j] > 0) {
			return lengths[i][j];
		}
		
		int row = matrix.length;
		int col = matrix[0].length;
		int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
		int max = 1;
		
		for(int[] dir : dirs) {
			
			int r = i + dir[0];
			int c = j + dir[1];
			
			if(-1 < r && r < row && -1 < c && c < col &&//
					matrix[r][c] > matrix[i][j]) {
				int path = dfs(matrix, lengths, r, c);
				max = Math.max(path + 1, max);
			}
		}
		lengths[i][j] = max;
		return max;
	}
	
}
